public final class busqueda_local3 extends Ejercicio
{ 
	public int[] Vo1, Vo2;
	public int cruces;
	
	protected Resultado DGIB
	(
			int n1, int v1[], int n2, int v2[], int m, Eje v1v2[],
			int np1, int vp1[], int np2, int vp2[], int mp, Eje vp1vp2[]
	){
		Resultado res = new Resultado();

		int i,j, N1 = n1+np1, N2 = n2+np2, M = m+mp;
		Nodo[] V1 = new Nodo[N1], V2 = new Nodo[N2];
		Eje[] V1V2 = new Eje[M];
		int[] ind = new int[np1], ind2 = new int[np2];
		Grado[] GV1 = new Grado[N1], GV2 = new Grado[N2];
		
		/*for( i = 0; i < n1; i++ )
			V1[i] = new Nodo(v1[i],false);
		
		for( i = 0; i < np1; i++ )
			V1[i + n1] = new Nodo(vp1[i],true);
		
		for( i = 0; i < n2; i++ )
			V2[i] = new Nodo(v2[i],false);
		
		for( i = 0; i < np2; i++ )
			V2[i + n2] = new Nodo(vp2[i],true);*/
		
		Hconstructiva constructiva = new Hconstructiva();
		constructiva.DGIB(n1, v1, n2, v2, m, v1v2, np1, vp1, np2, vp2, mp, vp1vp2);
		
		for(i = 0; i < N1; i++)
		{
			if(esta(vp1,constructiva.Vo1[i]))
			{
				V1[i] = new Nodo(constructiva.Vo1[i],true);
			}
			else
			{
				V1[i] = new Nodo(constructiva.Vo1[i],false);
			}
		}
		for(i = 0; i < N2; i++)
		{
			if(esta(vp2,constructiva.Vo2[i]))
			{
				V2[i] = new Nodo(constructiva.Vo2[i],true);
			}
			else
			{
				V2[i] = new Nodo(constructiva.Vo2[i],false);
			}
		}

		for( i = 0; i < m; i++ )
			V1V2[i] = v1v2[i];
		
		for( i = 0; i < mp; i++ )
			V1V2[m+i] = vp1vp2[i];
		
		int grado = 0;
		
		for(i = 0; i < N1; i++)
		{
			grado = 0;
			for(j = 0; j < M; j++ )
			{
				if( V1V2[j].origen == V1[i].valor )
				{
					grado++;
				}
			}
			GV1[i] = new Grado(V1[i].valor, grado);
		}
		
		grado = 0;
		
		for(i = 0; i < N2; i++)
		{
			grado = 0;
			for(j = 0; j < M; j++ )
			{
				if( V1V2[j].destino == V2[i].valor )
				{
					grado++;
				}
			}
			GV2[i] = new Grado(V2[i].valor, grado);
		}
		
		
		this.cruces = constructiva.cruces;
		//solucion optima
		this.Vo1 = new int[N1];
		this.Vo2 = new int[N2];
		
		localSearch
		(
			V1, N1,
			V2, N2,
			V1V2, M,
			GV1, GV2,
			ind,ind2,np1,np2
		);
		
		cruces = cantidadCruces(Vo1,N1,Vo2,N2,V1V2,M);
		
		res.kid = cruces;
		res.n_iv1 = N1;
		res.iv1 = Vo1; 
		res.n_iv2 = N2;
		res.iv2 = Vo2;		
		
		return res;
	}
	
	public void localSearch
	(
		Nodo[] IV1, int N1,
		Nodo[] IV2, int N2,
		Eje[] IV1V2, int M,
		Grado[] GV1, Grado[] GV2,
		int[] ind, int[] ind2,int np1,int np2
	)
	{
		int crucesmenos,pasos=0,cantcruces;
		int[] V1 = new int [N1], V2 = new int[N2];
		int j = 0,k = 0,i = 0, gradoMax = 0;
		int indice = 0;
		boolean invertido = false;
		
		for( i = 0; i < N1; i++ )
		{
			if( gradoMax < GV1[i].grado && IV1[i].incremental)
			{
				gradoMax = GV1[i].grado;
				indice = i;
				ind[j] = i;
			}
		}
		j++;
		
		for( i = 0; i < N2; i++ )
		{
			if( gradoMax < GV2[i].grado && IV2[i].incremental)
			{
				gradoMax = GV2[i].grado;
				indice = i;
				ind2[k] = i;
				invertido = true;
			}
		}
		k++;
		
		if(invertido)
		{
			crucesmenos = Vecindad(IV2,N2,IV1,N1,IV1V2,M,GV1,GV2,indice,invertido);
		}
		else
		{
			crucesmenos = Vecindad(IV1,N1,IV2,N2,IV1V2,M,GV1,GV2,indice,invertido);
		}
		cantcruces = cruces - crucesmenos;
		
		if(j >= np1)
		{
			j = 0;
		}
		if(k >= np2)
		{
			k = 0;
		}
		
		while( pasos < (N1+N2)/4 )
		{
			gradoMax = 0;
			invertido = false;
			
			for( i = 0; i < N1; i++ )
			{
				if( gradoMax < GV1[i].grado && !esta(ind,i)&& IV1[i].incremental )
				{
					gradoMax = GV1[i].grado;
					indice = i;
					ind[j] = i;
				}
			}
			j++;
			
			for( i = 0; i < N2; i++ )
			{
				if( gradoMax < GV2[i].grado && !esta(ind2,i) && IV2[i].incremental)
				{
					gradoMax = GV2[i].grado;
					indice = i;
					ind2[k] = i;
					invertido = true;
				}
			}
			k++;
			
			cruces = cantcruces;
			if (invertido)
			{
				crucesmenos = Vecindad(IV2,N2,IV1,N1,IV1V2,M,GV1,GV2,indice,invertido);
			}
			else
			{
				crucesmenos = Vecindad(IV1,N1,IV2,N2,IV1V2,M,GV1,GV2,indice,invertido);
			}
			cantcruces = cruces - crucesmenos;
			pasos++;
			if(j >= np1)
			{
				j = 0;
			}
			if(k >= np2)
			{
				k = 0;
			}
		}

		for(int m = 0; m < N1; m++)
		{
			V1[m] = IV1[m].valor ;
		}
			
		for(int m = 0; m < N2; m++)
		{
			V2[m] = IV2[m].valor;
		}
			
		System.arraycopy(V1, 0,this.Vo1, 0, N1); 
		System.arraycopy(V2, 0,this.Vo2, 0, N2); 
	}
	
	private int Vecindad
	(
			Nodo Vmovil[], int Nmovil,
			Nodo Vfijo[], int Nfijo,
			Eje V1V2[], int M, Grado[] GV1,Grado[] GV2,
			int indice, boolean invertido
	){
		int k, l, n,c=0, best_i = 0, best_c = 0,aux=0,res=0;
		Nodo v;
		
		v = Vmovil[indice];
		best_i = indice;
		k = 0;
		n = indice;
		best_c = 0;
		
		for(int j = 0; j < M; j++)
		{
			if( invertido )
			{
				if(V1V2[j].destino == v.valor)
				{
					best_c = best_c + CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
					aux = best_c;
				}
			}
			else
			{
				if(V1V2[j].origen == v.valor)
				{
					best_c = best_c + CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
					aux = best_c;
				}
			}
		}
		
		while( k < Nmovil)//ubico a v,en donde genera menos cruces
		{	
			if(k == 0)
			{
				for( l = n; l > k; l-- )
				{
					swap(Vmovil, l,l-1);
				}
			}
			else
			{
				swap(Vmovil,n,k);
			}
			
			c = 0;
			
			for(int j = 0; j < M; j++)
			{
				if( invertido )
				{
					if(V1V2[j].destino == v.valor)
					{
						c = c + CrucesDelEje(Vfijo, Nfijo, Vmovil, Nmovil, V1V2, M,V1V2[j]);
					}
				}
				else
				{
					if(V1V2[j].origen == v.valor)
					{
						c = c + CrucesDelEje(Vmovil, Nmovil, Vfijo, Nfijo, V1V2, M,V1V2[j]);
					}
				}
			}
			
			if(c < best_c)
			{
				best_i = k;
				best_c = c;
			}

			n = k;
			k++;
		}

		for( l = n; l > best_i; l-- )
		{
			swap(Vmovil, l,l-1);
			if(invertido)
			{
				swap(GV2, l,l-1);
			}
			else
			{
				swap(GV1, l,l-1);
			}
		}

		res = (aux - best_c);

		return res;
	}

}
